package com.yxp.offer;

import com.yxp.util.ListNode;

import java.util.List;

/**
 * @Auther : yxpweb
 * @Date : 2021/8/14 9:26
 * @Description: 剑指 Offer 24. 反转链表
 * 2021年8月21日11:14:54 新增一个递归实现
 */
public class Problem24 {

    public static void main(String[] args) {
        ListNode head = ListNode.initListNode();
        System.out.println(head.toString());
        Problem24 problem24 = new Problem24();
        ListNode listNode = problem24.reverseList2(head);
        System.out.println(listNode.toString());
    }

    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode tempNode = head;
        int size = 1;
        while (tempNode.next != null) {
            size++;
            tempNode = tempNode.next;
        }
        int[] arr = new int[size];
        tempNode = head;
        for (int i = size - 1; i >= 0; i--) {
            arr[i] = tempNode.val;
            tempNode = tempNode.next;
        }
        ListNode tailNode = new ListNode(arr[0]);
        tempNode = tailNode;
        for (int i = 1; i < arr.length; i++) {
            tempNode.next = new ListNode(arr[i]);
            tempNode = tempNode.next;
        }
        return tailNode;
    }

    /**
     * 令F(node)为问题:反转以node为头节点的单向链表；
     * 一般，我们需要考虑F(n)和F(n-1)的关系，那么这里，如果n代表以node为头节点的单向链表，那么n-1就代表以node.next为头节点的单向链表.
     * 所以，我们令F(node.next)为问题：反转以node.next为头节点的单向链表；
     * 那么，F(node)和F(node.next)之间的关系是？这里我们来简单画个图，假设我们反转3个节点的链表：
     * 1 -> 2 -> 3
     * 那么，F(node=1)=F(node=2)+?
     * 这里假设子问题F(node=2)已经解决，那么我们如何解决F(node=1)：
     * 很明显，我们需要反转node=2和node=1， 即 node.next.next=node; 同时 node.next=null;
     * 所以，这个问题就可以是：F(node=1)=F(node=2)+ 反转node=2和node=1
     *
     * @param head
     * @return 迭代做法
     */
    public ListNode reverseList1(ListNode head) {
        if (head == null || head.next == null) {  //终止条件并不难想
            return head;
        }
        ListNode node = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return node;  //按上面的例子，F(node=1)和F(node=2)它俩反转后的头节点是同一个
    }

    /**
     *
     * @param head
     * @return 递归做法
     */
    public ListNode reverseList2(ListNode head) {
        ListNode preNode = null;
        ListNode curNode = head;
        while (curNode != null) {
            ListNode nextNode = curNode.next;
            curNode.next = preNode;
            preNode = curNode;
            curNode = nextNode;
        }
        return preNode;
    }
}
